{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Values at Indices With K Set Bits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumIndicesWithKSetBits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算 K 置位下标对应元素的和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>请你用整数形式返回 <code>nums</code> 中的特定元素之 <strong>和</strong> ，这些特定元素满足：其对应下标的二进制表示中恰存在 <code>k</code> 个置位。</p>\n",
    "\n",
    "<p>整数的二进制表示中的 1 就是这个整数的 <strong>置位</strong> 。</p>\n",
    "\n",
    "<p>例如，<code>21</code> 的二进制表示为 <code>10101</code> ，其中有 <code>3</code> 个置位。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,10,1,5,2], k = 1\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>下标的二进制表示是： \n",
    "0 = 000<sub>2</sub>\n",
    "1 = 001<sub>2</sub>\n",
    "2 = 010<sub>2</sub>\n",
    "3 = 011<sub>2</sub>\n",
    "4 = 100<sub>2 \n",
    "</sub>下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。\n",
    "因此，答案为 nums[1] + nums[2] + nums[4] = 13 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,3,2,1], k = 2\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>下标的二进制表示是： \n",
    "0 = 00<sub>2</sub>\n",
    "1 = 01<sub>2</sub>\n",
    "2 = 10<sub>2</sub>\n",
    "3 = 11<sub>2\n",
    "</sub>只有下标 3 的二进制表示中存在 k = 2 个置位。\n",
    "因此，答案为 nums[3] = 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-values-at-indices-with-k-set-bits](https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-values-at-indices-with-k-set-bits](https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,10,1,5,2]\\n1', '[4,3,2,1]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nSetBits(self, num: int) -> int:\n",
    "        return sum(int(digit) for digit in \"{:b}\".format(num))\n",
    "\n",
    "\n",
    "    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:\n",
    "        return sum(\n",
    "            nums[i] if self.nSetBits(i) == k else 0\n",
    "            for i in range(len(nums))\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if bin(i)[2:].count('1') == k:\n",
    "                res += nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(0, n):\n",
    "            if i.bit_count() == k:\n",
    "                ans += nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums2 = []\n",
    "        res = 0\n",
    "        for num in range(n):\n",
    "            nums2.append(bin(num)[2:].count('1'))\n",
    "        for i in range(n):\n",
    "            if nums2[i] == k:\n",
    "                res += nums[i]\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
